/*
 * @lc app=leetcode.cn id=51 lang=cpp
 *
 * [51] N 皇后
 */

// @lc code=start
class Solution
{
private:
    vector<vector<string>> res;
    // row 行 col 列
    bool isValid(int row, int col, vector<string> &chess, int n)
    {
        //判断是否合法
        //列
        for (int i = 0; i < row; i++)
        {
            if (chess[i][col] == 'Q')
            {
                return false;
            }
        }
        //斜对角 45
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--)
        {
            if (chess[i][j] == 'Q')
            {
                return false;
            }
        }
        //斜对角 135
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++)
        {
            if (chess[i][j] == 'Q')
            {
                return false;
            }
        }
        return true;
    }
    void backtracking(int n, int row, vector<string> &chess)
    {
        //因为返回所有可能 所以void
        //这里用chess表示棋盘 string当数组用
        if (row == n)
        {
            res.push_back(chess);
            return;
        }
        for (int col = 0; col < n; col++)
        {
            if (isValid(row, col, chess, n))
            {
                chess[row][col] = 'Q';
                backtracking(n, row + 1, chess);
                chess[row][col] = '.';
            }
        }
    }

public:
    vector<vector<string>> solveNQueens(int n)
    {
        // n皇后问题 n个皇后放在nxn的棋盘上
        //可以抽象为树 每层一个皇后
        vector<string> chess(n, ".");
        backtracking(n, 0, chess);
        return res;
    }
};
// @lc code=end
